package com.lfg.leetcode.leetcode0;

import java.util.ArrayList;
import java.util.List;

public class No77combine {

    public static void main(String[] args) {
        List<List<Integer>> ret = combine(4, 2);
        System.out.println("[" + ret + "]");
    }

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ret = new ArrayList<>();
        if (k > n) {
            return ret;
        }
        List<Integer> nums = new ArrayList<>(k);
        combine(1, 0, n, k, nums, ret);
        return ret;
    }

    public static void combine(int data, int index, int n, int k, List<Integer> nums, List<List<Integer>> ret) {
        if (index + 1 == k) {
            for (int i = data; i <= n; i++) {
                nums.add(i);
                ret.add(new ArrayList<Integer>(nums));
                nums.remove(nums.size() - 1);
            }
            return;
        }
        for (int i = data; i < n; i++) {
            nums.add(i);
            combine(i + 1, index + 1, n, k, nums, ret);
            nums.remove(nums.size() - 1);
        }
    }

}

